package com.minglan.leetcode.java.solution2103;

/*
 * 2021年3月2日
 * 304. 二维区域和检索 - 矩阵不可变
 * 
给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
给定 matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

执行结果：
通过
执行用时：14 ms, 在所有 Java 提交中击败了99.00%的用户
内存消耗：44.2 MB, 在所有 Java 提交中击败了30.50%的用户
 */
public class NumMatrix {

    private int[][] matrix=null;
    
    public NumMatrix(int[][] matrix) {
        int x=matrix.length;
        int tmp=0;
        if(x>0) {
            int y=matrix[0].length;
            if(y>0) {
                this.matrix=new int[x][y];
                this.matrix[0][0]=matrix[0][0];
                for(int j=1;j<y;j++) {
                    this.matrix[0][j]=matrix[0][j]+this.matrix[0][j-1];
                }
                for(int i=1;i<x;i++) {
                    tmp=matrix[i][0];
                    this.matrix[i][0]=matrix[i][0]+this.matrix[i-1][0];
                    for(int j=1;j<y;j++) {
                        tmp=matrix[i][j]+tmp;
                        this.matrix[i][j]=tmp+this.matrix[i-1][j];
                    }
                }
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
    	if(col1==0&&row1==0) {
    		return this.matrix[row2][col2];
    	}
    	if(col1==0) {
    		return this.matrix[row2][col2]-this.matrix[row1-1][col2];
    	}
    	if(row1==0) {
    		return this.matrix[row2][col2]-this.matrix[row2][col1-1];
    	}
    	
    	return this.matrix[row2][col2]-this.matrix[row2][col1-1]-this.matrix[row1-1][col2]+this.matrix[row1-1][col1-1];
    }
    
	public static void main(String[] args) {
		/**
		 * Your NumMatrix object will be instantiated and called as such:
		 * NumMatrix obj = new NumMatrix(matrix);
		 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
		 */
		
		/*
		 * [[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],
		 * [2,1,4,3],[1,1,2,2],[1,2,2,4]]
		 */
		int[][] m={{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5}};
		logmatrix(m);
		NumMatrix obj = new NumMatrix(m);
		logmatrix(obj.matrix);
		System.out.println(obj.sumRegion(2, 1, 4, 3));
		System.out.println(obj.sumRegion(1, 1, 2, 2));
		System.out.println(obj.sumRegion(1, 2, 2, 4));

	}
	
	public static void logmatrix(int[][] m) {
		int x=m.length;
        if(x>0) {
            int y=m[0].length;
            if(y>0) {
            	for(int i=0;i<x;i++) {
            		for(int j=0;j<y;j++) {
            			System.out.print(m[i][j]+" ");
            		}
            		System.out.println("");
            	}

            }
        }
	}

}

